#include <iostream>
#include <stack>
using namespace std;

void hanoiRecursive(int n, char source, char target, char auxiliary) {
    if (n == 1) {
        cout << "Move disk 1 from " << source << " to " << target << endl;
        return;
    }

    hanoiRecursive(n - 1, source, auxiliary, target);
    cout << "Move disk " << n << " from " << source << " to " << target << endl;
    hanoiRecursive(n - 1, auxiliary, target, source);
}

void hanoiNonRecursive(int n, char source, char target, char auxiliary) {
    struct Node {
        int n;
        char source;
        char target;
        char auxiliary;
        bool isMoveNextDisk;
        Node(int n, char source, char target, char auxiliary, bool isMoveNextDisk) : 
            n(n), source(source), target(target), auxiliary(auxiliary), isMoveNextDisk(isMoveNextDisk) {}
    };

    stack<Node> stack;
    stack.push(Node(n, source, target, auxiliary, false));

    while (!stack.empty()) {
        Node current = stack.top();
        stack.pop();

        if (current.n == 1) {
            cout << "Move disk 1 from " << current.source << " to " << current.target << endl;
            if (current.isMoveNextDisk) {
                cout << "Move disk " << current.n << " from " << current.source << " to " << current.target << endl;
            }
        } else {
            if (current.isMoveNextDisk) {
                cout << "Move disk " << current.n << " from " << current.source << " to " << current.target << endl;
            } else {
                stack.push(Node(current.n - 1, current.auxiliary, current.target, current.source, false));
                stack.push(Node(current.n, current.source, current.target, current.auxiliary, true));
                stack.push(Node(current.n - 1, current.source, current.auxiliary, current.target, false));
            }
        }
    }
}

int main() {
    int n = 3; 

    cout << "Recursive solution:" << endl;
    hanoiRecursive(n, 'A', 'C', 'B');

    cout << "Non-recursive solution:" << endl;
    hanoiNonRecursive(n, 'A', 'C', 'B');

    return 0;
}